package algorithm;

import com.alibaba.fastjson.JSON;

import java.util.Arrays;

/**
 * Created by ZhuQianli on 2018/2/1.
 */
public class QuickSort {
    public static void main(String[] args) {
        int[] array = {3, 5, 7, 1, 1, 3};
        Arrays.sort(array); // 这里使用了双轴快排   详情自己看源码
        System.out.println(JSON.toJSONString(array));


        int[] array2 = {3,6,8,1,3,5,8,0};
        sort(array2, 0, array2.length - 1);
        System.out.println(JSON.toJSONString(array2));



    }

    // 1.取第一个数作为轴d
    // 2.假设为数组长度为10,则l初始化为1,r初始化为10
    // 3.r--,获取数组[r]上的数字t,t和d比较,如果t>=d,继续3;如果t<d,交换数组[l]和数组[r],继续4
    // 4.l++,获取数组[l]上的数字t,t和d比较,如果t>=d,交换数组[l]和数组[r],继续3;如果t<d,继续4
    // 5.当l等于r 一次比较结束
    public static void sort(int[] array, int left, int right) {
        if (left >= right) return;

        int d = array[left];
        int l = left;
        int r = right + 1;

        boolean flag = true;

        while (l != r) {
            if (flag) {
                // 步骤3
                int t = array[--r];
                if (t >= d) {
                    // 继续3
                } else {
                    // 交换
                    array[l] = t;
                    flag = false;
                }
            } else {
                //步骤4
                int t = array[++l];
                if (t >= d) {
                    // 交换
                    array[r] = t;
                    flag = true;
                } else {
                    // 继续4
                }
            }
        }

        array[l] = d;

        sort(array, left, l - 1);
        sort(array, r + 1, right);
    }

}
